﻿//力扣：1863. 找出所有子集的异或总和再求和
//链接：https://leetcode.cn/problems/sum-of-all-subset-xor-totals/description/


//方法：DFS+位运算
//
//所有⼦集可以解释为：每个元素选择在或不在⼀个集合中（因此，⼦集有 2^n 个）。
//本题我们需要求出所有⼦集，将它们的异或和相加。因为异或操作满⾜交换律，所以我们可以定义⼀个变量，直接记录当前状态的异或和。
//使⽤递归保存当前集合的状态（异或和），选择将当前元素添加⾄当前状态与否，并依次递归数组中下⼀个元素。
//当递归到空元素时，表⽰所有元素都被考虑到，记录当前状态（将当前状态的异或和添加⾄答案中）。
//
//递归流程：
//1. 递归结束条件：当前下标与数组⻓度相等，即已经越界，表⽰已经考虑到所有元素；
//    a.将当前异或和添加⾄答案中，并返回；
//2. 考虑将当前元素添加⾄当前状态，当前状态更新为与当前元素值的异或和，然后递归下⼀个元素；
//3. 考虑不选择当前元素，当前状态不变，直接递归下⼀个元素；
class Solution
{
public:
    int path;                   // 当前路径的异或值
    int sum;                    // 最终结果的异或和

    void dfs(vector<int>& nums, int pos)
    {
        sum += path;            // 将当前路径的异或值加入到结果中

        // 遍历当前数字的所有后续数字
        for (int i = pos; i < nums.size(); i++)
        {
            path ^= nums[i];    // 将当前数字与路径的异或值进行异或操作
            dfs(nums, i + 1);   // 递归调用，尝试添加下一个数字
            path ^= nums[i];    // 回溯，恢复路径的异或值(再次异或当前数字还是原来的路径)
        }
    }

    int subsetXORSum(vector<int>& nums)
    {
        dfs(nums, 0);           // 从位置0开始深度优先搜索
        return sum;             // 返回最终的异或和
    }
};
